// constructing roads
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e3;
int p[maxn];
int n, m;
struct face //存储数据
{
    int u, v, w;
} edge[maxn * maxn];
bool cmp(face a, face b) //权值排序
{
    return a.w < b.w;
}
void init() //并查集1
{
    for (int i = 1; i <= n; i++)
        p[i] = i;
}
int find(int x) //并查集2
{
    return x == p[x] ? x : p[x] = find(p[x]);
}
long long kruskal() //核心算法，记得用longlong，他的数据挺大的。
{
    long long ans = 0; //防止ans存不下
    init();
    sort(edge, edge + m, cmp); //此处就是将给的权值先排序
    for (int i = 0; i < m; i++)
    {
        int x = find(edge[i].u);
        int y = find(edge[i].v);
        if (x != y)
        {
            ans += edge[i].w;
            p[x] = y;
        }
    }
    return ans;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    while (scanf("%d", &n) != EOF) //但是注意输入，HDU - 1233 和HDU - 1863给的n和m不一样（切记注意）
    {
        m = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int a;
                scanf("%d", &a);
                edge[m].u = i;
                edge[m].v = j;
                edge[m].w = a;
                m++;
            }
        }
        int t;
        scanf("%d", &t);
        for (int i = 1; i <= t; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            edge[m].u = a;
            edge[m].v = b;
            edge[m].w = 0;
            m++;
        }
        printf("%lld\n", kruskal()); //longlong输出。
    }
    return 0;
}